Many color image output devices are not capable of displaying all of the colors in an input digital image due to the fact that they must be stored in a memory buffer with a reduced bit-depth. Likewise, it may also be desirable to represent an image using a reduced bit-depth in order to reduce the amount of bandwidth needed for the transmission of an image, or the amount of memory needed to store an image. For example, many computers may use an 8-bit or a 16 bit color representation to store an image that is to be displayed on a soft-copy display such as a CRT or an LCD screen. Such representations allow only 256 and 65,536 unique color values, respectively. This is significantly less than the 16,777,216 possible color values associated with a typical 24-bit color image that is conventionally used in many digital imaging applications.
In applications where it is necessary to represent an input image using a reduced number of colors, it is necessary to determine the set of colors to be included in the reduced set of colors. In some cases, a reduced set of colors may be determined ahead of time independent of the particular image being encoded. For example, 3-bits of color information (8 different levels) may be used for the red and green channels of an image, and 2-bits of color information (4 different levels) may be used for the blue channel of an image. This produces a lattice of 8×8×4=256 different color values that can be used to represent the input image using an 8-bit representation. The input digital image can be converted to the 8-bit representation simply by taking the highest 2- or 3-bits of each of the corresponding RGB channels. The result is an image that has quantization errors that can produce visible contours in the image in many circumstances. This color palette is referred to as the 3-3-2 palette and is used in a number of wireless devices such as the Ericsson T68 cell phone.
One method for minimizing the visibility of the quantization errors in the reduced bit-depth image is to use a multi-level halftoning algorithm to preserve the local mean of the color value. R. S. Gentile, E. Walowit and J. P. Allebach, “Quantization and multilevel halftoning of color images for near original image quality,” J. Opt. Soc. Am. A 7, 1019–1026 (1990) described various methods for quantization and multilevel halftoning of color images. One commonly used multi-level halftoning method is called error diffusion. The detail of error diffusion will be discussed later.
In wireless communication, there is usually a limit on the size of the file to be transmitted through the air and received by a targeted wireless device. For example, the current wireless communication standard requires that the file size should not exceed 3 kilo bytes. In the case of the EricssonT68 cell phone, let us assume that one would like to display an image of the size of 96×64 pixels on its color screen. Even after a digital color image is rendered by the 3-3-2 color palette and reduced to 1 byte per pixel, it takes 96×64=6144 bytes to simply store the indices to the color palette. In general, it is undesirable to compress the indices in a lossy fashion because any error in the index value could result in significant color distortion due to indexing error. Therefore, the indices are usually compressed using a lossless file format such as CompuServe GIF, or Portable Network Graphics (PNG) (see www.w3.org./Graphics/PNG), or the upcoming Joint Photographic Network Group recommended format referred to as JPEG 2000 (see www.jpeg.org), by taking advantage of the data redundancy because of correlation in the image structures. In addition, a dithering process such as error diffusion (see P. G. Roetling and R. P. Loce, “Digital halftoning,” in Digital Image Processing Methods, E. Dougherty, Ed. New York: Marcel Dekker, 1994.) is frequently employed to alleviate color quantization effect, due to the use of a display palette, in order to produce a visually more pleasing image. Because the image has been reduced to a small size, and more importantly, the amount of correlation is significantly reduced by the error diffusion process, which is of high-pass nature in terms of frequency response, it becomes extremely challenging to achieve the needed compression in order to get the file size below the required 3 kilo bytes. On one hand, compression is required to satisfy the bandwidth limitation. On the other hand, compression (including quantization, and resizing) inevitably reduces the image quality. In short, the requirements for small file size and good image quality are competing constraints.
Conventional systems are generally unable to provide a good solution given similar competing constraints. In U.S. Patent Application Publication No. 2002/0016818 A1, which is entitled “System and Methodology for Optimizing Delivery of Email Attachments for Disparate Devices” and was published on Feb. 7, 2002, Kirani and Whittington disclose system and methodology for optimizing delivery of email attachments for disparate devices. Kirani and Whittington compare the size of attached images to the capabilities of the types of the recipient client device, and pre-empt the delivery of the original format of those attachments if they are determined to be burdensome or overwhelming for the particular recipient device in use. In cases wherein these attachments would strain the capabilities of the recipient device's wireless bandwidth and/or display features, the original attachments are simply removed from the messages and saved in a network media-sharing repository, which can be subsequently accessed via a link (e.g., URL) referencing that storage address. Recipients can specify their wireless handheld device type, and opt to receive transformations of this type of attachment. In cases wherein the recipient has previously used and specified multiple types of client devices, Kirani and Whittington apply a transformation to the current attachment that corresponds to the least capable in the set of those multiple devices. Clearly, this process is cumbersome and the least capable device determines the image quality for all devices.
There is therefore a need to provide a method for rendering and compressing a digital image for display on a display device using a display palette and having a display resolution less than the original image resolution, where the transmission channel also imposes a limit on the maximum file size.